We consider the pricing of American put options in a model-independent setting: that is, we do not assume that asset prices behave according to a given model, but aim to draw conclusions that hold in any model. We incorporate market information by supposing that the prices of European options are known. In this setting, we are able to provide conditions on the American Put prices which are necessary for the absence of arbitrage. Moreover, if we further assume that there are finitely many European and American options traded, then we are able to show that these conditions are also sufficient. To show sufficiency, we construct a model under which both American and European options are correctly priced at all strikes simultaneously. In particular, we need to carefully consider the optimal stopping strategy in the construction of our process.